//节点类
class Node{
    constructor(element){
        this.element = element;
        this.next = null;
    }
}

//创建单向链表的类

class LinkedList{
    constructor(){
        this.head = null;//记录第一个节点
        this.count = 0; //记录链表有节点数量
    }
    //push 在链表的末尾添加
    push(element){
        let node = new Node(element); //创建新的节点
        //1.第一种情况 链表为空
        if(this.head === null){
            this.head = node;
        }else{
            //2.链表不为空
            let current = this.head;
            //2.1 查找最后一个节点
            while(current.next){
                current = current.next;
            }
            current.next = node;
        }
        this.count++;
    }

    //获取指定下标的节点
    getElementAt(index){ //1
        let current = this.head;
        for(let i = 0;i<index;i++){
            current = current.next;
        }
        return current
    }

    //删除 通过下标来删除
    removeAt(index){
        //1.边界值的判断
        if(index >= 0 && index < this.count){
            let current = this.head;
            if(index === 0){
                //在链表开头删除
                this.head = current.next; //b
            }else{
                let prev = this.getElementAt(index-1); //删除节点的上一个节点
                current = prev.next; //要删除的节点
                prev.next = current.next;
            }
            this.count--;
            return current.element
        }else{
            return undefined
        }
    }

    //插入
    insert(element,index){
        //1.边界值的判断
        if(index >= 0 && index <= this.count){
            let node = new Node(element);
            //1.1在开头插入
            if(index === 0){
                if(this.head === null){
                     //1.1.1 当前链表为空
                    this.head = node;
                }else{
                     //1.1.2 当前链表不为空
                    let current = this.head;
                    this.head = node;
                    node.next = current;
                }
            }else{
                let prev = this.getElementAt(index-1); //a
                let current = prev.next; //b
                prev.next = node;
                node.next = current;
            }   
            this.count++;
        }else{
            return false
        }
    }

    //查找下标
    indexOf(element){
        let current = this.head;
        for(let i = 0;i<this.count;i++){
            if(current.element === element){
                return i
            }
            current = current.next;
        }
        return -1
    }
    //删除元素
    remove(element){
        //1.找下标
        let index = this.indexOf(element);
        //2.根据下标来删除
        this.removeAt(index);
    }

    //获取链表的个数
    size(){
        return this.count
    }

    //当前链表是否为空
    isEmpty(){
        return this.count === 0
    }

    //获取首元素
    getHead(){
        return this.head
    }
}

let l = new LinkedList();

// l.push('a');
l.push('b');
// console.log(l.removeAt(0));

// l.insert('c',2);
// console.log(l.indexOf('y'));

console.log(l.getHead())

l.remove('b');

console.log(l.size())

console.log(l.isEmpty())
console.log(l)

//1.单链表 

//2.双链表

//3.面试题 2~3